package com.leetcode;

/**
 * 1140. 石子游戏 II (中等)
 * 爱丽丝和鲍勃继续他们的石子游戏。许多堆石子排成一行，每堆都有正整数颗石子piles[i]。游戏以谁手中的石子最多来决出胜负。
 * 爱丽丝和鲍勃轮流进行，爱丽丝先开始。最初，M = 1。
 * 在每个玩家的回合中，该玩家可以拿走剩下的前X堆的所有石子，其中1 <= X <= 2M。然后，令M = max(M, X)。
 * 游戏一直持续到所有石子都被拿走。
 * 假设爱丽丝和鲍勃都发挥出最佳水平，返回爱丽丝可以得到的最大数量的石头。
 */
public class LeetCode1140 {

    public static void main(String[] arg0) {
        int[] piles = new int[]{3, 4, 1, 1, 8, 10};
        System.out.println("爱丽丝可以得到的最大数量的石头 = " + stoneGameII(piles));
    }

    /**
     * 动态规划
     */
    public static int stoneGameII(int[] piles) {
        int length = piles.length;
        int sum = 0;
        int[][] dp = new int[length][length + 1];

        for (int i = length - 1; i >= 0; i--) { // 从后往前
            sum += piles[i];

            for (int m = 1; m <= length; m++) {
                if ((i + 2 * m) >= length) {
                    dp[i][m] = sum;
                } else {
                    for (int x = 1; x <= 2 * m; x++) {
                        dp[i][m] = Math.max(dp[i][m], sum - dp[i + x][Math.max(m, x)]);
                    }
                }
            }
        }

        return dp[0][1];
    }

}
